GATE PYQ

Binary Search Tree

Q11.
Suppose the numbers 7,5,1,8,3,6,0,9,4,2 are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering on natural numbers. What is the in-order traversal sequence of the resultant tree?

Q12.
While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is

Q13.
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?

Q14.
Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)? I. 3, 5, 7, 8, 15, 19, 25 II. 5, 8, 9, 12, 10, 15, 25 III. 2, 7, 10, 8, 14, 16, 20 IV. 4, 6, 7, 9 18, 20, 25

Q15.
The number of ways in which the numbers 1,2,3,4,5,6,7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _____. Note: The height of a tree with a single node is 0.

Q16.
What are the worst-case complexities of insertion and deletion of a key in a binary search tree?

Q17.
How many distinct BSTs can be constructed with 3 distinct keys?

Q18.
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81,537,102,439,285,376,305 II. 52,97,121,195,242,381,472 III. 142,248,520,386,345,270,307 IV. 550,149,507,395,463,402,270 Suppose the BST has been unsuccessfully searched for key 273. Which all of the above sequences list nodes in the order in which we could have encountered them in the search?

Q19.
You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,...,n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

Q20.
A Binary Search Tree (BST) stores values in the range 37 to 573. Consider the following sequence of keys. I. 81,537,102,439,285,376,305 II. 52,97,121,195,242,381,472 III. 142,248,520,386,345,270,307 IV. 550,149,507,395,463,402,270 Which of the following statements is TRUE?